A Critical Path Approach to Analyzing Parallelism of Algorithmic Variants. Application to Cholesky Inversion

摘要

Algorithms come with multiple variants which are obtained by changing themathematical approach from which the algorithm is derived. These variants offera wide spectrum of performance when implemented on a multicore platform and weseek to understand these differences in performances from a theoretical pointof view. To that aim, we derive and present the critical path lengths of eachalgorithmic variant for our application problem which enables us to determine alower bound on the time to solution. This metric provides an intuitive grasp ofthe performance of a variant and we present numerical experiments to validatethe tightness of our lower bounds on practical applications. Our case study isthe Cholesky inversion and its use in computing the inverse of a symmetricpositive definite matrix.